package com.lw.leetcode.tree.b;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 1104. 二叉树寻路
 *
 * @Author liw
 * @Date 2021/6/21 10:52
 * @Version 1.0
 */
public class PathInZigZagTree {

    public static void main(String[] args) {
        PathInZigZagTree test = new PathInZigZagTree();
        for (int i = 10; i > 0; i--) {
            List<Integer> integers = test.pathInZigZagTree(i);
            System.out.println(integers);
        }
    }

    public List<Integer> pathInZigZagTree(int label) {
        int item = label;
        int count = 1;
        while (item != 1) {
            item >>= 1;
            count++;
        }
        List<Integer> list = new ArrayList<>(count);
        for (int i = count - 1; i > 0; i--) {
            list.add(label);
            label >>= 1;
            count--;
            label = (1 << (count - 1)) + ((1 << count) - 1) - label;
        }
        list.add(1);
        Collections.reverse(list);
        return list;
    }
}
